1. Field of the Invention
The present invention relates to a switch having multiple input buffers and multiple output buffers. Especially, an implementing method for a scheduler driving a crossbar fabric having multiple ingress lines and egress lines, and a queue management method guaranteeing the order of packets which belong to the same flow. Hereinafter, the switch having multiple input buffers and multiple output buffers in the present invention is referred to as “multiple input/output-queued switch(MIOQ switch)”.
2. Description of the Related Art
In order to access the Internet nowadays, a very high-speed switch(or router, hereinafter referred to as “switch”) for optical communication is indispensable. The usual Internet backbone is composed of high-speed electrical switches which are connected via fiber-optic links. Currently, a single fiber can have multiple wavelength channels each of which operates at 2.5 Gpbs or 10 Gbps, and the overall transmission capacity through optical fibers has increased to over a few terabits per second. Compared to the tremendous capacity of optical links, the switching capacity enhancement of electrical switches becomes a relative bottleneck for the Internet backbone. Moreover, there is a pressing demand for the guarantee of quality-of-service(QoS) in the use of the Internet, which is another responsibility of backbone switches.
The high bandwidth requirement of switches makes the input-queued switch illustrated in FIG. 1 an attractive candidate since its memory and switch fabric can operate only at the line speed. However, this input-queued switch cannot achieve a comparable QoS performance to the output-queued switch illustrated in FIG. 2. To satisfy both the requirements of high switching capacity and QoS guarantees simultaneously, the combined input/output-queued(CIOQ) switch illustrated in FIG. 3 has been proposed as a solution. In the CIOQ switch, the switch fabric operates at a faster speed than the link rate by the speedup s, and in a single time slot, at most s packets can be delivered from each input buffer to each output buffer, which requires buffering of the packets at outputs as well as inputs.
There have been many research works on the minimum speedup to match the performance of an output-queued switch. S. T. Chuang, et al. showed that a speedup of 2 in a CIOQ switch can provide the same delay performance of an output-queued switch using the stable marriage matching(SMM) algorithm [S. T. Chuang, A. Goel, N. McKeown and B. Prabhakar, “Matching Output Queueing with a Combined Input and Output Queued Switch”, IEEE J. Select. Areas Commun., Vol. 17, pp. 1030-1039, December 1999].
However, the speedup of the switch fabric needs memories with shortened access time and requires a scheduler to make scheduling decisions within a reduced time, which is a non-trivial difficulty even for a speedup of only 2. Therefore, in a recent approach to achieve the comparable performance of an output-queued switch with no speedup, a parallel switching architecture(PSA) has been studied by S. Iyer, et al. [S. Iyer, A. Awadallah, and N. McKeown, “Analysis of a Packet Switch with Memories Running Slower than the Line-Rate”, IEEE INFOCOM'2000, Vol. 2, pp. 529-537, March, 2000]. The PSA is composed of input demultiplexers, output multiplexers and parallel switches. In the PSA, an incoming stream of packets are spread packet-by-packet by a demultiplexer across the parallel switches, then recombined by a multiplexer at each output.
While the parallel switch does not require any speedup, the performance of the parallel switch depends on a quite complex centralized distribution algorithm, which has a similar complexity to that of the SMM algorithm used for a CIOQ switch. Therefore, its implementation at a high operation rate is not practical for the emulation of output-queueing.